package com.shujujiegou.红黑树.红黑树实现;

import com.alibaba.fastjson.JSON;

import java.io.Serializable;

public class RBTree<T extends Comparable<T>> implements Serializable {
    private RBNode<T> root; // 根节点

    public RBTree() {

    }

    private void leftNode(RBNode<T> x) {
        // 将y的左子节点赋值给x的右子节点，同时将x赋值给y的左子节点的父节点（y的左子节点非空时）
        RBNode<T> y = x.right;
        x.right = y.left;
        if(y.left != null) {
            y.left.parent = x;
        }

        // 将x的父节点p(非空时)赋值给y的父节点，同时更新p的子节点为y(左或右);
        y.parent = x.parent;
        if(x.parent == null) {
            this.root = y;
        } else {
            if(x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        }

        // 将y的左子节点设置为x,将x的父节点设置为x
        y.left = x;
        x.parent = y;
    }

    public void rightNode(RBNode<T> y) {
        // 将y左子节点的右子节点设置为x的左子节点，同时将x左子节点的右子节点的父节点指向x
        RBNode<T> x = y.left;
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }

        // 将y的父节点设置为x的父节点， 同时设置y的父节点的子节点为x
        x.parent = y.parent;
        if (null == y.parent) {
            this.root = x;
        } else {
            if (y.parent.left == y) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        }

        // 将y的父节点设置为x,同时设置x的右子节点为y
        x.parent = y;
        y.right = x;
    }

    public void insert(T key) {
        RBNode<T> node = new RBNode<T>(true,key,null,null,null , false);
        if(node != null) {
            insertNode(node);
        }
    }

    public void insertNode(RBNode<T> node) {
        RBNode<T> parent = null;
        RBNode<T> current = this.root;

        // 1.找到插入位置
        while (null != current) {
            parent = current;
            int compareResult = node.key.compareTo(current.key);
            if(compareResult < 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        node.parent = parent; // 找到插入位置

        // 2.判断node是左子节点还是右子节点
        if(parent != null) {
            if(node.key.compareTo(parent.key) < 0) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        } else {
            this.root = node;
        }

        // 3.利用旋转操作将其修正为一颗红黑树
        insertFixUp(node);
    }

    private void insertFixUp(RBNode<T> node) {
        RBNode<T> parent,gparent;//定义父节点和祖父节点

        // 需要修正的条件：父亲节点存在，且父亲节点为红色
        while(node.parent != null && node.parent.color) {
            parent = node.parent;
            gparent = parent.parent; // 父节点存在且父节点为红色，那么祖父节点一定是存在的

            // 如果父亲节点是祖父节点的左子节点
            if(parent == gparent.left) {
                // 获得叔叔节点
                RBNode<T> uncle = gparent.right;
                // case1: 叔叔节点也是红色的
                if(uncle != null && uncle.color) {
                    parent.color = false;
                    uncle.color = false;
                    gparent.color = true;
                    node = gparent; // 将位置放到祖父节点
                    continue;
                }
                // case2：叔叔节点是黑色的，且当前节点是右子节点
                if(node == parent.right) {
                    leftNode(parent); // 从父节点处执行左侧旋转
                    RBNode<T> tmp = parent; // 将父节点和当前节点进行对调，为右旋转做准备
                    parent = node;
                    node = tmp;
                }

                // case3：叔叔节点是黑色的，且当前节点是左子节点
                parent.color = false;
                gparent.color = true;
                rightNode(gparent);
            } else {
                // 获得叔叔节点
                RBNode<T> uncle = gparent.left;
                // case1: 叔叔节点也是红色的
                if(uncle != null && uncle.color) {
                    parent.color = false;
                    uncle.color = false;
                    gparent.color = true;
                    node = gparent; // 将位置放到祖父节点
                    continue;
                }
                // case2：叔叔节点是黑色的，且当前节点是左子节点
                if(node == parent.left) {
                    rightNode(parent); // 从父节点处执行左侧旋转
                    RBNode<T> tmp = parent; // 将父节点和当前节点进行对调，为左旋转做准备
                    parent = node;
                    node = tmp;
                }

                // case3：叔叔节点是黑色的，且当前节点是左子节点
                parent.color = false;
                gparent.color = true;
                leftNode(gparent);
            }
        }

        // 当node根节点的时候
        this.root.color = false; //将根节点设置为黑色
    }

    public static void main(String[] args) {
        RBTree<Integer> tree = new RBTree<Integer>();
        tree.insert(0);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(5);
        tree.insert(6);
        tree.insert(7);
        tree.insert(8);
        tree.insert(9);
        tree.insert(10);
        tree.insert(11);
        tree.insert(12);
        tree.insert(13);
        tree.insert(14);

        System.out.println(JSON.toJSON(tree));
    }
}
